λ¬Έμ
μκ·Όμ΄λ λ¬Έμμ΄μ νλ° λ¬Έμμ΄μ μ¬μ΄ λμλ€. νλ° λ¬Έμμ΄μ΄ νλ°νλ©΄ κ·Έ λ¬Έμλ λ¬Έμμ΄μμ μ¬λΌμ§λ©°, λ¨μ λ¬Έμμ΄μ ν©μ³μ§κ² λλ€.
νλ°μ λ€μκ³Ό κ°μ κ³Όμ μΌλ‘ μ§νλλ€.
- λ¬Έμμ΄μ΄ νλ° λ¬Έμμ΄μ ν¬ν¨νκ³ μλ κ²½μ°μ, λͺ¨λ νλ° λ¬Έμμ΄μ΄ νλ°νκ² λλ€. λ¨μ λ¬Έμμ΄μ μμλλ‘ μ΄μ΄ λΆμ¬ μλ‘μ΄ λ¬Έμμ΄μ λ§λ λ€.
- μλ‘ μκΈ΄ λ¬Έμμ΄μ νλ° λ¬Έμμ΄μ΄ ν¬ν¨λμ΄ μμ μλ μλ€.
- νλ°μ νλ° λ¬Έμμ΄μ΄ λ¬Έμμ΄μ μμ λκΉμ§ κ³μλλ€.
μκ·Όμ΄λ λͺ¨λ νλ°μ΄ λλ νμ μ΄λ€ λ¬Έμμ΄μ΄ λ¨λμ§ κ΅¬ν΄λ³΄λ €κ³ νλ€. λ¨μμλ λ¬Έμκ° μλ κ²½μ°κ° μλ€. μ΄λλ "FRULA"λ₯Ό μΆλ ₯νλ€.
νλ° λ¬Έμμ΄μ κ°μ λ¬Έμλ₯Ό λ κ° μ΄μ ν¬ν¨νμ§ μλλ€.
μ λ ₯
- 첫째 μ€μ λ¬Έμμ΄μ΄ μ£Όμ΄μ§λ€. λ¬Έμμ΄μ κΈΈμ΄λ 1λ³΄λ€ ν¬κ±°λ κ°κ³ , 1,000,000λ³΄λ€ μκ±°λ κ°λ€.
- λμ§Έ μ€μ νλ° λ¬Έμμ΄μ΄ μ£Όμ΄μ§λ€. κΈΈμ΄λ 1λ³΄λ€ ν¬κ±°λ κ°κ³ , 36λ³΄λ€ μκ±°λ κ°λ€.
- λ λ¬Έμμ΄μ λͺ¨λ μνλ²³ μλ¬Έμμ λλ¬Έμ, μ«μ 0, 1, ..., 9λ‘λ§ μ΄λ£¨μ΄μ Έ μλ€.
μΆλ ₯
- 첫째 μ€μ λͺ¨λ νλ°μ΄ λλ ν λ¨μ λ¬Έμμ΄μ μΆλ ₯νλ€.
π Logic
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Graph {
final int[] graph;
int[] discovered;
boolean[] fin;
int answer = 0;
int graph_size;
public Graph(int size) {
graph_size = size + 1;
this.graph = new int[graph_size];
discovered = new int[graph_size];
fin = new boolean[graph_size];
}
public void AddElement(int x, int y) {
graph[x] = y;
}
public int solution() {
for (int i=1; i < graph_size; i++) this.search(i);
return graph_size - 1 - this.answer;
}
public void search(int node) {
if (discovered[node] == 1) return;
discovered[node] = 1;
int next = graph[node];
if (discovered[next] == 0) search(graph[node]);
else {
if (!fin[next]) {
// λ€μ κ° μ μ μ΄ λ°©λ¬Έμ νμΌλ μμ§ λλμ§ μμ, μ¦ μ¬μ΄ν΄μ΄ μμ±λμ§ μμ μν
answer++;
for (int i=next; i!=node; i=graph[i]) {
answer++;
}
}
}
fin[node] = true;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T > 0) {
int size = sc.nextInt();
Graph g = new Graph(size);
for (int i = 1; i <= size; i++) {
int tmp = sc.nextInt();
g.AddElement(i, tmp);
}
System.out.println(g.solution());
T-=1;
}
sc.close();
}
}
βοΈ Review
-
μ²μμλ
replaceAll()ν¨μλ₯Ό μ¬μ©ν΄μ λ§€μ° κ°λ¨ν μ½λλ‘ κ΅¬ννμΌλ, 47%μμ λ©λͺ¨λ¦¬ μ΄κ³Όκ° λ΄λ€.- λΉμ°ν μ΄λ κ² μ¬μΈ 리λ μλ€κ³ μκ°νκ³ , κ²μνμ 보λ
replace()ν¨μκ° λ©λͺ¨λ¦¬λ₯Ό λ§μ΄ μ¬μ©νλ λ©μλλΌλ κ²μ μμλ€.
- λΉμ°ν μ΄λ κ² μ¬μΈ 리λ μλ€κ³ μκ°νκ³ , κ²μνμ 보λ
π μΆμ²
Baekjoon : https://www.acmicpc.net/problem/9935